// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏，实际上就是暴搜
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 8：
// 给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。
// 返回 所有可能得到的字符串集合 。以 任意顺序 返回输出。
//
//        示例 1：
//
//        输入：s = "a1b2"
//        输出：["a1b2", "a1B2", "A1b2", "A1B2"]
//        示例 2:
//
//        输入: s = "3z4"
//        输出: ["3z4","3Z4"]
//
//
//        提示:
//
//        1 <= s.length <= 12
//        s 由小写英文字母、大写英文字母和数字组成

// 解题思路：
// 每次只考虑 pos 位置的字符
// 先将字母添加到 path 中，再考虑 pos + 1 位置字符，继续递归，本层结束要回溯
// 如果遇到字母，就改变大小写，添加到 path 中，再考虑 pos + 1 位置字符，继续递归，本层结束要回溯
// pos == s.length() 时，收集结果

import java.util.ArrayList;
import java.util.List;

public class LetterCasePermutation {
    List<String> ret;
    StringBuilder path;
    char[] sArr;
    public List<String> letterCasePermutation(String s) {
        ret = new ArrayList<>();
        path = new StringBuilder();
        sArr = s.toCharArray();
        dfs(sArr, 0);
        return ret;
    }
    public void dfs(char[] sArr, int pos){
        if(pos == sArr.length){
            ret.add(path.toString());
            return;
        }
        // 不改变
        path.append(sArr[pos]);
        dfs(sArr, pos + 1);
        path.deleteCharAt(path.length() - 1);

        // 改变
        if(sArr[pos] >= 'a' && sArr[pos] <= 'z'){
            path.append((char)(sArr[pos] - ('a' - 'A')));
            dfs(sArr, pos + 1);
            path.deleteCharAt(path.length() - 1);
        }else if(sArr[pos] >= 'A' && sArr[pos] <= 'Z'){
            path.append((char)(sArr[pos] + ('a' - 'A')));
            dfs(sArr, pos + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
